package hot100.双指针.单行到底.窗口.哈希.固定窗口;

import java.util.*;

/** 438-找到字符串中所有字母异位词
 */

/**
 * 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
 *
 * 输入: s = "cbaebabacd", p = "abc"
 * 输出: [0,6] 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词 和 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
 *
 * 求字符串里 连续的子字符串 符合为目标异位词的 索引起始数组
 * 1.滑动 + Array.sort(String.toArray) 后者考虑换 -> 哈希表做当前窗口值
 * 2.思考与 会变窗口.longestNoRepeatSubstring3 -> 需要考虑重叠的情况
 */
public class misplaceWord438 {

    public List<Integer> me(String s, String p) {
        List<Integer> result = new ArrayList<>();
        if (s.length() < p.length()) return result;

        int[] pCount = new int[26];
        int[] sCount = new int[26];

        for (char c : p.toCharArray()) pCount[c - 'a']++;

        int windowSize = p.length();
        for (int i = 0; i < s.length(); i++) {
            sCount[s.charAt(i) - 'a']++;
            if (i >= windowSize -1) { /**固定的窗口 天然head-tail重合表达(head当前元素索引) 需考虑开头结尾问题***/
                if (Arrays.equals(pCount, sCount)) {
                    result.add(i - windowSize + 1);
                }
                sCount[s.charAt(i - windowSize +1) - 'a']--;
            }

        }
        return result;
    }

    public List<Integer> gpt(String s, String p) {
        List<Integer> result = new ArrayList<>();
        if (s.length() < p.length()) return result;

        int[] pCount = new int[26];
        int[] sCount = new int[26];

        for (char c : p.toCharArray()) pCount[c - 'a']++;

        int windowSize = p.length();
        for (int i = 0; i < s.length(); i++) {
            sCount[s.charAt(i) - 'a']++;

            if (i >= windowSize) {
                sCount[s.charAt(i - windowSize) - 'a']--;
            }

            if (Arrays.equals(pCount, sCount)) {
                result.add(i - windowSize + 1);
            }
        }
        return result;
    }


    /** String -×>List<Character> -×>Collections.sort(List)
     *  String ->char[] ->Array.sort(char[])
     *  String ->char[] ->new Array(char[]) -> Collections.sort(Array)**/
    public List<Integer> seemLike49(String s, String p) {
        if (p.length() > s.length()) { return new ArrayList<>();}

        List<Integer> result = new ArrayList<>();

        //int head = 0;
        Arrays.sort(p.toCharArray());
        for (int i = 0; i <= s.length() - p.length(); i++) { // i 是起始位置
            String substring = s.substring(i, i + p.length()); //取值 √

            char[] charArray = substring.toString().toCharArray(); //排序
            Arrays.sort(charArray);

            if (p.equals(new String(charArray))) { result.add(i);} //序后对比
            //head++;
        }
        return result;
    }


    public static void main(String[] args) {
        misplaceWord438 a = new misplaceWord438();
        System.out.println(a.gpt("cbaabcdbacb", "abc"));
    }
}